package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * Binary search tree where objects can be inserted.
 * 
 * @author Axel Sundbom, Johannes Sjölund, Tim Danielsson
 */
public class BinaryTree {

	public Node root;
	public int size;
	// Number of operations for lookup. Incremented for every new recursion
	// step.
	static public int lookupOperations;
	// Number of operations for insert. Incremented for every new recursion
	// step.
	static public int insertOperations;
	// Number of operations for string comparison. Number of characters
	// compared.
	static public int compareOperations;
	// Number of operations for rotating on a node.
	static public int rotateOperations;

	public BinaryTree() {
		root = null;
		size = 0;
	}

	/**
	 * Reset counters
	 */
	public void resetCounters() {
		lookupOperations = 0;
		insertOperations = 0;
		compareOperations = 0;
		rotateOperations = 0;
	}

	/**
	 * Reset tree
	 */
	public void resetTree() {
		size = 0;
		root = null;
	}

	/**
	 * A node in the tree, can hold two other nodes Has ha key from language A
	 * and translations to B
	 */
	public static class Node {

		Node left;
		Node right;
		int height;
		String key;
		ArrayList<String> translations;

		/**
		 * Compare two strings.
		 * 
		 * @param a
		 *            A string
		 * @param b
		 *            Another string
		 * @param n
		 *            Letters left in recursive comparison
		 * @return Returns -1 if (a > b) and 1 if (a < b), 0 if (a == b).
		 */
		private static int compare(String a, String b, int n) {
			compareOperations++;
			if (n == Math.min(a.length(), b.length())) {
				if (a.length() < b.length()) {
					return 1;
				} else if (a.length() > b.length()) {
					return -1;
				} else {
					return 0;
				}
			} else {
				if (a.charAt(n) < b.charAt(n)) {
					return 1;
				} else if (a.charAt(n) > b.charAt(n)) {
					return -1;
				} else {
					return compare(a, b, n + 1);
				}
			}
		}

		/**
		 * Create a new node.
		 * 
		 * @param key
		 *            A word from language A
		 * @param translation
		 *            String, a new translation from A to B
		 */
		public Node(String key, String translation) {
			this.key = key;
			translations = new ArrayList<String>();
			translations.add(translation);
			left = null;
			right = null;
			height = 1;
		}

		/**
		 * Compares this node against another.
		 * 
		 * @param n
		 *            Node to compare against
		 * @return -1 if less than, 0 if equal, 1 if greater than
		 */
		public int compare(Node n) {
			return compare(key, n.key, 0);
		}

		/**
		 * Compare this node against a string.
		 * 
		 * @param s
		 *            String to compare with
		 * @return -1 if less than, 0 if equal, 1 if greater than
		 */
		public int compare(String s) {
			return compare(key, s, 0);
		}

		@Override
		/**
		 * returns a String representation of a Node
		 */
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("[");
			builder.append("key=");
			builder.append(key);
			builder.append(", height=");
			builder.append(height);
			builder.append(", translations=(");
			for (String s : translations) {
				builder.append(s + ", ");
			}
			builder.append(")]");
			return builder.toString();
		}

	}

	/**
	 * Checks the balance of the nodes
	 * 
	 * @param node
	 *            Node on which to check balance on
	 * @return int The height difference of the subtrees under this node.
	 */
	private static int getBalance(Node node) {
		if (node == null) {
			return 0;
		}
		return getHeight(node.left) - getHeight(node.right);
	}

	/**
	 * Makes sure the height is returned correctly formatted.
	 * 
	 * @param node
	 *            A node to check weight on
	 * @return The height of a node
	 */
	private static int getHeight(Node node) {
		if (node == null) {
			return 0;
		}
		return node.height;
	}

	/**
	 * Recursively iterating the nodes in the tree in numeric order from left to
	 * right.
	 * 
	 * @param node
	 *            The node on which to start the walk.
	 * @return A list of ordered nodes.
	 */
	public static List<Node> inOrderWalk(Node node) {
		List<Node> nodes = new ArrayList<Node>();
		if (node.left != null) {
			nodes.addAll(inOrderWalk(node.left));
		}
		nodes.add(node);
		if (node.right != null) {
			nodes.addAll(inOrderWalk(node.right));
		}
		return nodes;
	}

	/**
	 * Insert a new node to the tree.
	 * 
	 * @param value
	 *            The node to be inserted.
	 * @param node
	 *            The node we stand on in current recursive step.
	 * @return The new root. All subtrees under this root will be balanced.
	 */
	private Node insert(Node value, Node node) {

		insertOperations++;
		int direction = node.compare(value);

		if (direction == 0) {
			node.translations.addAll(value.translations);
			return node;

		} else if (direction < 0) {
			if (node.left == null) {
				node.left = value;
			} else {
				node.left = insert(value, node.left);
			}
		} else {
			if (node.right == null) {
				node.right = value;
			} else {
				node.right = insert(value, node.right);
			}
		}

		node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
		int balance = getBalance(node);

		// Left-left case
		if (balance > 1 && node.left != null && node.left.compare(value) < 0) {
			return rotateRight(node);
		}
		// Right-right case
		if (balance < -1 && node.right != null && node.right.compare(value) > 0) {
			return rotateLeft(node);
		}
		// Left-right case
		if (balance > 1 && node.left != null && node.left.compare(value) > 0) {
			node.left = rotateLeft(node.left);
			return rotateRight(node);
		}
		// Right-left case
		if (balance < -1 && node.right != null && node.right.compare(value) < 0) {
			node.right = rotateRight(node.right);
			return rotateLeft(node);
		}
		return node;
	}

	/**
	 * Insert a new translation.
	 * 
	 * @param key
	 *            A word from language A.
	 * @param translation
	 *            The translation in language B.
	 */
	public void insert(String key, String translation) {
		Node newNode = new Node(key, translation);

		if (root == null) {
			root = newNode;
			size++;
		} else {
			root = insert(newNode, root);
			size++;
		}
	}

	/**
	 * Search for a node which has this string as key.
	 * 
	 * @param root
	 *            The node on which to begin the search.
	 * @param key
	 *            The key to search for.
	 * @return The node which has this key.
	 */
	private Node lookupNode(Node root, String key) {
		// Test if checking empty
		if (key.length() <= 0 || root == null)
			return null;
		else {
			// Compare nodes
			int result = root.compare(key);
			lookupOperations++;

			// Recurse
			if (result == 0)
				return root;
			else if (result < 0)
				return this.lookupNode(root.left, key);
			else
				return this.lookupNode(root.right, key);
		}
	}

	/**
	 * Search the tree for a key string.
	 * 
	 * @param key
	 *            The key to look for
	 * @return Node result, the node which has this key.
	 */
	public Node lookupNode(String key) {
		return lookupNode(root, key);
	}

	/**
	 * Search the tree fort the translations of this string.
	 * 
	 * @param key
	 *            The key to look for
	 * @return The list of translations.
	 */
	public List<String> lookup(String key) {
		return lookupNode(root, key).translations;
	}

	/**
	 * Print a string representation of the tree.
	 */
	public void printTree() {
		List<Node> nodes;
		nodes = inOrderWalk(root);
		for (Node n : nodes) {
			System.out.print(n.key + ",");
		}
		System.out.println("");
	}

	/**
	 * Do a left rotation of the subtree which has this node as root.
	 * 
	 * @param node
	 *            Node to rotate on
	 * @return The new root
	 */
	public Node rotateLeft(Node node) {

		// temps
		Node newRoot = node.right;
		Node temp = newRoot.left;

		// rotate left
		newRoot.left = node;
		node.right = temp;

		// update heights
		node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
		newRoot.height = Math.max(getHeight(newRoot.left),
				getHeight(newRoot.right)) + 1;

		// 4 pointers changed
		rotateOperations += 4;

		return newRoot;

	}

	/**
	 * Do a right rotation of the subtree which has this node as root.
	 * 
	 * @param node
	 *            Node to rotate on
	 * @return New root
	 */
	public Node rotateRight(Node node) {

		// temps
		Node newRoot = node.left;
		Node temp = newRoot.right;

		// rotate right
		newRoot.right = node;
		node.left = temp;

		// update heights
		node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
		newRoot.height = Math.max(getHeight(newRoot.left),
				getHeight(newRoot.right)) + 1;

		// 4 pointers changed
		rotateOperations += 4;

		return newRoot;

	}
}
